package com.java.container;



/**
 * @program: java_basic_knowledge
 * @description:
 * @author: CaoYong
 * @create: 2021-04-19 09:32
 **/
public class LinkedHashMapKnowledge {


    // LinkedHashMap是HashMap的子类
    // LinedHashMap内部维护了一个单独的双向链表，每个节点即位于哈希表中也位于双向链表中，链表顺序默认是插入顺序，也可以配置为访问顺序
    public static class HowTodDefineLinkedHashMap<K, V> extends HashMapKnowledge.HowToDefineHashMap<K,V> {

        private Entry<K, V> header; // 双向链表的头结点
        private boolean accessOrder; // 表示按访问顺序还是插入顺序


        // LinkedHashMap中的Entry继承自HashMap的Entry，在其基础上添加了两个成员变量before和after，以此实现双向链表
        public static class Entry<K, V> extends HashMapKnowledge.HowToDefineHashMap.Entry<K, V> {
            Entry<K, V> before;
            Entry<K, V> after;

            public Entry(int hash, K key, V value, HashMapKnowledge.HowToDefineHashMap.Entry<K, V> next) {
                super(hash, key, value, next);
            }

            // 删除当前节点
            private void remove() {
                before.after = after;
                after.before = before;
            }

            private void addBefore(Entry<K, V> existingEntry) {
                after = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }

            // 如果是按访问顺序的则将该节点移动到链表的末尾
            void recordAccess(HashMapKnowledge.HowToDefineHashMap m) {
                HowTodDefineLinkedHashMap<K, V> lm = (HowTodDefineLinkedHashMap<K, V>) m;
                if (lm.accessOrder) {
                    lm.modCount ++;
                    remove();
                    addBefore(lm.header);
                }
            }

            //将节点从表中移除
            void recordRemoval(HashMapKnowledge.HowToDefineHashMap<K, V> m) {
                remove();
            }
        }

        // 重写HashMap的init()方法。初始化一个Entry对象，前驱和后继都指向自己
        void init() {
            header = new Entry<>(-1, null, null, null);
            header.before = header.after = header;
        }

        // 重写HashMap的addEntry方法,添加完后悔调用removeEldestEntry()检查是否应该删除老节点，如果是则调用removeEntryForKey()进行删除
        @Override
        void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex);
            Entry<K, V> eldest = header.after;
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            }
        }

        private boolean removeEldestEntry(Entry<K,V> eldest) {
            return false;
        }

        // 重写HashMap的createEntry()方法，新建的节点在加入Hash表的同事也加入到链表中
        @Override
        void createEntry(int hash, K key, V value, int bucketIndex) {
            HashMapKnowledge.HowToDefineHashMap.Entry<K, V> old = table[bucketIndex];
            Entry<K, V> e = new Entry<>(hash, key, value, old);
            table[bucketIndex] = e;
            e.addBefore(header);
            size++;
        }

        // 重写HasMap的get()方法， get后调用recordAccess方法，调整该节点到链表末尾
        @Override
        public V get(Object key) {
            Entry<K, V> e = (Entry<K, V>) getEntry(key);
            if (e == null) {
                return null;
            }
            e.recordAccess(this);
            return e.value;
        }

    }

    public static void howToUseLinkedHashMap() {
        HowTodDefineLinkedHashMap<String, Integer> linkedHashMap = new HowTodDefineLinkedHashMap<>();
        linkedHashMap.init();
        linkedHashMap.put("c", 100);
        linkedHashMap.put("d", 200);
        linkedHashMap.put("a", 500);
        linkedHashMap.put("d", 300);


    }

    public static void main(String[] args) {
        howToUseLinkedHashMap();
    }
}
